{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8e2b0372",
   "metadata": {},
   "source": [
    "## 桶排序\n",
    "根据数据元素的某种特征，设计对应的算法，进而达到加快排序的目的。\n",
    "例如：假如待排序的数组每一个元素的取值都在区间[0, 1]内随机分布，就可以使用桶排序来加快排序速度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e4a7ef41",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Before bucket sort : [0.35, 0.35, 0.31, 0.68, 0.94, 0.15, 0.7, 0.04, 0.16, 0.21, 0.57, 0.86, 0.26, 0.83, 0.31, 0.71, 0.28, 0.32, 0.75, 0.94]\n",
      "After bucket sort : []\n"
     ]
    }
   ],
   "source": [
    "## 桶排序\n",
    "import math\n",
    "import numpy\n",
    "def insertion_sort(array, a):       # 插入排序将元素插入桶内列表\n",
    "    i = 0\n",
    "    while i < len(array):\n",
    "        if array[i] > a:\n",
    "            break\n",
    "        i += 1\n",
    "    array.insert(i, a)\n",
    "    \n",
    "\n",
    "def bucket_sort(A):\n",
    "    # 根据数值中元素的个数来设置桶的个数\n",
    "    # 每一个桶内是一个存储数值的链表\n",
    "    bucket_list = [[] for _ in range(len(A))]\n",
    "    for a in A:\n",
    "        bucket_num = math.floor(len(A) * a)       # 获得元素对应的桶号\n",
    "        insertion_sort(bucket_list[bucket_num], a)\n",
    "    sorted_array = []\n",
    "    for bucket in bucket_list:\n",
    "        if len(bucket) > 0:\n",
    "            sorted_array.extend(bucket)\n",
    "    return sorted_array\n",
    "\n",
    "N = 20\n",
    "A = []\n",
    "for n in range(N):\n",
    "    f = round(numpy.random.uniform(0, 1), 2)    # 精确到小数点后两位\n",
    "    A.append(f)\n",
    "print(f\"Before bucket sort : {A}\")\n",
    "A = bucket_sort(A)\n",
    "print(f\"After bucket sort : {A}\")\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
